package org.example.disjoinSet;

/**
 * 不相交集合（并查集合）
 */
public class DisjoinSet {
    int[] s;
    int[] size;

    public DisjoinSet(int size) {
        this.s = new int[size];
        for (int i = 0; i < size; i++) {
            s[i] = i;
            this.size[i] = 1;
        }
    }
    //find 查找老大值
    public int find(int x){
        if (s[x] == x){
            return x;
        }
        return find(s[x]);
        // return s[x] = find(s[x]); (优化代码--路径压缩)
    }

    //union 是让两个集合‘相交’，即选出新的老大，x,y 是原老大的索引
    public void union(int x,int y){
        if (size[x] < size[y]){     //y的小弟多，所以y当老大
            s[y] = x;
            size[y] = size[x] + size[y];
        }else {         //x的小弟多，所以x当老大
            s[x] = y;
            size[x] = size[x] + size[y];
        }
    }

    @Override
    public String toString() {
        return super.toString();
    }

    public static void main(String[] args) {

    }
}
